#leetcode题目279：完全平方数
#难度：中等
#时间复杂度：O(n)
#空间复杂度：O(n)
#方法：动态规划

#题目理解：
# 类似于背包问题，一个固定容量的背包，装满这个背包，最少需要多少个物品。
#简化成：当前选择的数字，当前剩余的空间。

from typing import List

class Solution:
    def numSquares(self, n: int) -> int:
        """
        完全平方数
        给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。
        你需要让组成和的完全平方数的个数最少。
        """
        # 生成所有小于等于n的完全平方数
        perfect_squares = []
        i = 1
        while i * i <= n:
            perfect_squares.append(i * i)
            i += 1
        
        length = len(perfect_squares)
        
        # 初始化记忆化数组，-1表示未计算
        dp = [[-1] * (n + 1) for _ in range(length)]
        
        return self.process(perfect_squares, 0, n, dp)
    
    def process(self, perfect_squares: List[int], index: int, rest: int, dp: List[List[int]]) -> int:
        
        """递归处理函数 - 记忆化搜索
        :param perfect_squares: 完全平方数列表
        :param index: 当前考虑的完全平方数索引
        :param rest: 剩余需要组成的数
        :param dp: 记忆化数组
        :return: 最少需要的完全平方数个数
        """
        # 基础情况1：剩余为0，说明已经组成完成
        if rest == 0:
            return 0
        
        # 基础情况2：所有完全平方数都考虑完了，但rest不为0
        if index == len(perfect_squares):
            return float('inf')
        
        # 记忆化检查：如果已经计算过，直接返回
        if dp[index][rest] != -1:
            return dp[index][rest]
        
        current_square = perfect_squares[index]
        result = float('inf')
        
        # 尝试使用当前完全平方数0次、1次、2次...
        i = 0
        while current_square * i <= rest:
            # 递归计算使用i个当前完全平方数后的最少个数
            sub_result = self.process(perfect_squares, index + 1, rest - current_square * i, dp)
            
            # 如果子问题有解，更新结果
            if sub_result != float('inf'):
                result = min(result, i + sub_result)
            
            i += 1
        
        # 存储结果到记忆化数组
        dp[index][rest] = result
        return result


#测试数据
n = 12
#预期输出：3，12=4+4+4
solution = Solution()
print(solution.numSquares(n))

n = 13
#预期输出：2，13=4+9
solution = Solution()
print(solution.numSquares(n))